# 方法一全排列，超时
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        s = str(n)
        l = len(s)
        if l == 1:
            return n & (n - 1) == 0
        ans = []
        path = [0] * l
        on_path = [False] * l
        # 对字符串进行有重复数字的全排列
        def dfs(i):
            if i == l and path not in ans:
                ans.append(path.copy())
                return
            for j, on in enumerate(on_path):
                if not on:
                    path[i] = s[j]  # 从没有选的数字中选一个
                    on_path[j] = True  # 已选上
                    dfs(i + 1)
                    on_path[j] = False
        dfs(0)
        # 判断每一个排列是否是二的幂
        for i in range(len(ans)):
            if ans[i][0] == "0":# 第一个数为0直接跳过
                continue
            temp = int("".join(ans[i]))
            if temp & (temp - 1) == 0:
                return True
        return False
# 方法二
pow_two_sorted_str_set = {''.join(sorted(str(1 << i))) for i in range(30)}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        s = ''.join(sorted(str(n)))
        return s in pow_two_sorted_str_set